/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._242;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 *
 * 示例 1:
 *
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 * 示例 2:
 *
 * 输入: s = "rat", t = "car"
 * 输出: false
 * 说明:
 * 你可以假设字符串只包含小写字母。
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._242
 * @ClassName: ValidAnagram
 * @Author: linyaonan
 * @Date: 2019/12/17 14:19
 */
public class ValidAnagram {

    public boolean isAnagram(String s, String t) {

        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        if (s.length() != t.length()) {
            return false;
        }
        if (s.length() == 0) {
            return true;
        }
        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        // 遍历s字符串
        char[] schars = s.toCharArray();
        for (char schar : schars) {
            if (sMap.containsKey(schar)) {
                Integer count = sMap.get(schar);
                sMap.put(schar, ++count);
            } else {
                sMap.put(schar, 1);
            }
        }

        // 遍历t字符串
        char[] tchars = t.toCharArray();
        for (char tchar : tchars) {
            if (!sMap.containsKey(tchar)) {
                return false;
            }
            if (tMap.containsKey(tchar)) {
                Integer count = tMap.get(tchar);
                ++count;
                Integer sCount = sMap.get(tchar);
                if (count > sCount) {
                    return false;
                }
                tMap.put(tchar, count);
            } else {
                tMap.put(tchar, 1);
            }
        }
        return true;
    }

    public boolean isAnagram2(String s, String t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        if (s.length() != t.length()) {
            return false;
        }
        if (s.length() == 0) {
            return true;
        }

        int[] sNums = new int[26];
        int[] tNums = new int[26];
        // 遍历s字符串
        for (char ch : s.toCharArray()) {
            sNums[ch - 'a']++;
        }
        // 遍历t字符串
        for (char ch : t.toCharArray()) {
            int index = ch - 'a';
            if (sNums[index] < tNums[index]) {
                return false;
            }
            tNums[index]++;
        }
        // 只可能有26中key
        for (int i = 0; i < 26; i++) {
            if (sNums[i] != tNums[i]) {
                return false;
            }
        }
        return true;
    }
}
